5.2 Develop an iterative version of the permute method (from Lab 9). Here is the method specification: /** * Finds all permutations of a specified String. * * @param s - the String to be permuted. * * @return a String representation of all the permutations, with a line separator * (that is, "\n") after each permutation. */ public static String permute (String s) For example, if the original string is "BADCGEFH", the value returned would be ABCDEFGH ABCDEFHG ABCDEGFH ABCDEGHF ABCDEHFG and so on. Test your method with the same PermuteTest method developed in Lab 9 to test the recursive version. Hint: One strategy starts by converting s to a character array c. Then the elements in c can be easily swapped with the help of the index operator, [ ]. To get the first permutation, use the static method sort in the Arrays class of java.util. To give you an idea of how the next permutation can be constructed from the current permutation, suppose, after some permutations have been printed, c = ["A", "H", "E", "G", "F", "D", "C", "B"] What is the smallest index whose character will be swapped to obtain the next permutation? It is index 2, because the characters at indexes 3 through 7 are already in reverse alphabetical order: 'G' > 'F' > 'D' > 'C' > 'B'. We swap 'E' with 'F', the smallest character greater than 'E' at an index greater than 2. After swapping, we have c = ["A", "H", "F", "G", "E", "D", "C", "B"] We then reverse the characters at indexes 3 through 7 to get those characters into increasing order: c = ["A", "H", "F", "B", "C", "D", "E", "G"], the next higher permutation after 'A', 'H', 'E', 'G', 'F', 'D', 'C', 'B'. Here is an outline: public static String permute (String s) { int n = s.length(); boolean finished = false; char[ ] c = s.toCharArray(); String perms = ""; Arrays.sort (c); // c is now in ascending order while (!finished) { perms += String.valueOf (c)); // In 0 ... n-1, find the highest index p such that // p = 0 or c [p - 1] < c [p]. ... if (p == 0) finished = true; else { // In p ... n-1, find the largest index i such that c [i] > c [p - 1]. ... // Swap c [i] with c [p - 1]. // Swap c [p] with c [n-1], swap c [p+1] with c[n-2], // swap c [p+2] with c [n-3], ... ... } // else } // while return perms; } // method permute In the above example, p - 1 = 2 and i = 4, so c [p - 1], namely, 'E' is swapped with c [i], namely, 'F'. Explain how strings with duplicate characters are treated differently in this method than in the recursive version. | |
| View Solution | |
| << Back | Next >> |